#include <stdio.h>
#include <grass/G3d.h>

#define G_254_SQUARE 64516
#define G_254_TIMES_2 508

#define G_RLE_OUTPUT_CODE(code) (*((unsigned char *) dst++) = (code))
#define G_RLE_INPUT_CODE(codeP) (*(codeP) = *((unsigned char *) src++))

/*---------------------------------------------------------------------------*/

static int
G_rle_codeLength  (int length)

{
  register int lPrime;
  int codeLength;

  if (length == -1) return 2;
  if (length < 254) return 1;
  if (length < G_254_TIMES_2) return 2;
  if (length < G_254_SQUARE) return 3;
  
  codeLength = 0;
  lPrime = length;
  while ((lPrime = lPrime / 254) != 0) codeLength++;
  return codeLength + 2;
}

/*---------------------------------------------------------------------------*/

static char *
rle_length2code  (int length, char *dst)

{
  register int lPrime;

  if (length == -1) { /* stop code */
    G_RLE_OUTPUT_CODE (255);
    G_RLE_OUTPUT_CODE (255);

    return dst;
  }

  if (length < 254) {
    G_RLE_OUTPUT_CODE (length);

    return dst;
  }

  if (length < G_254_TIMES_2) { /* length == 254 + a; a < 254 */
    G_RLE_OUTPUT_CODE (255);
    G_RLE_OUTPUT_CODE (length % 254);

    return dst;
  }

  if (length < G_254_SQUARE) {/* length = 254 * b + a; b, a < 254 */
    G_RLE_OUTPUT_CODE (254);  /* this if-clause included for efficiency only */
    G_RLE_OUTPUT_CODE (length / 254);
    G_RLE_OUTPUT_CODE (length % 254);

    return dst;
  }

  /* length = 254 ^ c + 254 * b + a; b, a < 254 */

  lPrime = length;
  while ((lPrime = lPrime / 254) != 0) G_RLE_OUTPUT_CODE (254);
    
  length %= G_254_SQUARE;

  G_RLE_OUTPUT_CODE (length / 254);
  G_RLE_OUTPUT_CODE (length % 254);

  return dst;
}
  
/*---------------------------------------------------------------------------*/

static char *
rle_code2length  (char *src, int *length)

{
  int code;

  if (G_RLE_INPUT_CODE (length) < 254) return src; /* length < 254 */

  if (*length == 255) { /* length == 254 + a; a < 254 */
    if (G_RLE_INPUT_CODE (length) == 255) {
      *length = -1;
      return src;
    }

    *length += 254;
    return src;
  }

  G_RLE_INPUT_CODE (&code);
  if (code < 254) { /* length = 254 * b + a; b, a < 254 */ 
    G_RLE_INPUT_CODE (length);/* this if-clause included for efficiency only */
    *length += 254 * code;

    return src;
  }

  /* length = 254 ^ c + 254 * b + a; b, a < 254 */

  *length = G_254_SQUARE;
  while (G_RLE_INPUT_CODE (&code) == 254) *length *= 254;
  
  *length += 254 * code;
  G_RLE_INPUT_CODE (&code);
  *length += code;
  
  return src;
}

/*---------------------------------------------------------------------------*/

int
G_rle_count_only  (char *src, int nofElts, int eltLength)

{
  int length, nofEqual;
  char *head, *tail, *headStop, *headStop2;

  if (nofElts <= 0) G3d_fatalError ("trying to encode 0-length list");

  length = 0;
  nofEqual = 1;
  head = src + eltLength;
  tail = src;

  headStop = src + nofElts * eltLength;

  while (head != headStop) {
    headStop2 = head + eltLength;

    while (head != headStop2) {
      if (*head != *tail) {
	length += G_rle_codeLength (nofEqual) + eltLength;
	nofEqual = 1;
	tail = headStop2 - eltLength;
	break;
      }
      head++;
      tail++;
    }
    
    if (head == headStop2) {
      nofEqual++;
      continue;
    }

    head = headStop2;
  }
  length += G_rle_codeLength (nofEqual) + eltLength;

  return length + G_rle_codeLength (-1);
}

/*---------------------------------------------------------------------------*/

void
G_rle_encode  (char *src, char *dst, int nofElts, int eltLength)

{
  int length, nofEqual;
  char *head, *tail, *headStop, *headStop2;

  if (nofElts <= 0) G3d_fatalError ("trying to encode 0-length list");

  length = 0;
  nofEqual = 1;
  head = src + eltLength;
  tail = src;

  headStop = src + nofElts * eltLength;

  while (head != headStop) {
    headStop2 = head + eltLength;

    while (head != headStop2) {
      if (*head != *tail) {
	dst = rle_length2code (nofEqual, dst);
	tail = headStop2 - eltLength * (nofEqual + 1);
	head = tail + eltLength;
/*	printf ("equal %d char %d\n", nofEqual, *tail);*/
	while (tail != head) *dst++ = *tail++;
	length += G_rle_codeLength (nofEqual) + eltLength;
	nofEqual = 1;
	tail = headStop2 - eltLength;
	break;
      }
      head++;
      tail++;
    }
    
    if (head == headStop2) {
      nofEqual++;
      continue;
    }

    head = headStop2;
  }

  dst = rle_length2code (nofEqual, dst);
  tail = headStop - eltLength * nofEqual;
  head = tail + eltLength;
  while (tail != head) *dst++ = *tail++;
  length += G_rle_codeLength (nofEqual) + eltLength;
  dst = rle_length2code (-1, dst);
  length += G_rle_codeLength (-1);
  rle_code2length (dst - 2, &nofEqual);
}

/*---------------------------------------------------------------------------*/

void
G_rle_decode  (char *src, char *dst, int nofElts, int eltLength, int *lengthEncode, int *lengthDecode)

{
  int nofEqual;
  char *src2, *srcStop, *src2Stop, *dstFirst;

  srcStop = src + nofElts * eltLength;
  dstFirst = dst;

  while (src != srcStop) {
    src = rle_code2length (src, &nofEqual);

    if (nofEqual == -1) {
      *lengthEncode = src - (srcStop - nofElts * eltLength);
      *lengthDecode = dst - dstFirst;
      return;
    }

    while (nofEqual--) {
      src2 = src;
      src2Stop = src2 + eltLength;
      while (src2 != src2Stop) *dst++ = *src2++;
    }
    src += eltLength;
  }

  G3d_fatalError ("G_rle_decode: string ends prematurely");
}

/*---------------------------------------------------------------------------*/

void
test_rle ()

{
  char c[100];
  int length;

  do {
    printf ("length? ");
    scanf ("%d", &length);
    printf ("length = %d\n", length);
    printf ("codeLength %d   ", G_rle_codeLength (length));
    (void) rle_length2code (length, c);
    length = 0;
    (void) rle_code2length (c, &length);
    printf ("output length %d\n\n", length);
  } while (1);
}
